1. Field of the Invention
The invention relates to a packet switch and a method of scheduling a packet switch, and more particularly to a packet switch and a method of scheduling a packet switch in both of which an order of precedence in a request to transfer a packet is shuffled.
2. Description of the Related Art
With recent remarkable development in Internet, core nodes constituting a network, such as a switch or a router, are required to have a high capacity to transfer a packet. As a switch used for transferring a packet, there are known a common buffer type switch, an output buffer type switch, and an input buffer type switch.
FIG. 1 is a block diagram of an example of a conventional common buffer type switch. The illustrated common buffer type switch is comprised of a multiplexer 1202, a common buffer 1204, a demultiplexer 1205, and a bus 1203 electrically connecting the multiplexer 1202, the common buffer 1204 and the demultiplexer 1205 to one another.
The multiplexer 1202 receives packets through a plurality of input ports 12011 to 1201n, and transmits the received packets into the bus 1203. The packets transmitted into the bus 1203 are written into the common buffer 1204 in order. A controller (not illustrated) reads the packets out of the common buffer 1204 in accordance with a predetermined algorithm, and transmits the thus read-out packets into the bus 1203. The packets transmitted into the bus 1203 are supplied to the demultiplexer 1205. The demultiplexer 1205 demultiplexes the received packets in order, and outputs the thus multiplexed packet through one of a plurality of output ports 12061 to 1206n. Thus, there is accomplished a function of switching a packet.
Since the common buffer type switch can include a large-sized common buffer, the common buffer type switch could have superior traffic characteristic.
However, since the common buffer 1204 is accessed by all the input ports 12011 to 1201n and all the output ports 12061 to 1206n, it is required to increase a rate at which the packets are transferred through the bus 1203. However, since there is limitation in increasing such a rate, it would be quite difficult to accomplish a high-rate switch comprised of a common buffer type switch.
FIG. 2 is a block diagram of an example of a conventional output buffer type switch. The illustrated output buffer type switch is comprised of a switch 1302 and a plurality of output buffers 13041 to 1304n each of which receives an output signal transmitted from the switch 1302.
The switch 1302 receives packets through a plurality of input ports 13011 to 1301n, switches the thus received packets, and outputs the thus switched packets to the output buffers 13041 to 1304n. The output buffers 13041 to 1304n stores the received packets therein. The output buffers 13041 to 1304n transmit the packets stored therein through the output ports 13051 to 1305n in order.
If two or more packets are transmitted to one of the output ports 12061 to 1206n, only one of the packets is output through the output port, and the rest of the packets are made wait.
In the output buffer type switch, the packets may be concurrently transmitted to a certain one output port from all the input ports. Accordingly, a rate at which a packet is transferred has to be equalized to X multiplied by n, wherein X indicates a transfer rate necessary for switching a single packet, and “n” means the number of the input or output ports. As a result, it would be quite difficult to accomplish a high-rate switch comprised of an output buffer type switch, similarly to the above-mentioned common buffer type switch.
Hence, there is predominantly used an input buffer type switch as a high-rate switch.
FIG. 3 is a block diagram of an example of a conventional input buffer type switch. The illustrated input buffer type switch is comprised of a plurality of input buffers 14021 to 1402n, a scheduler 1405, and a switch 1406.
The input buffers 14021 to 1402n receive packets through input ports 14011 to 1401n, and stores the thus received packets therein. Then, the input buffers 14021 to 1402n transmit requests 14041 to 1404n to the scheduler 1405 in order to transfer the stored packets to an output port 14071 to 1407n designated by address data.
The scheduler 1405 schedules the output ports 14071 to 1407n to which the packets are to be transmitted, based on the requests 14041 to 1404n transmitted from the input buffers 14021 to 1402n, and transmits results of scheduling the output ports 14071 to 1407n to the switch 1406. On receipt of the results from the scheduler 1405, the switch outputs the packets through the designated output ports 14071 to 1407n. 
In addition, the scheduler 1405 transmits grants indicative of an allowance to transfer a packet, to the input buffers 14021 to 1402n, based on the results of scheduling the output ports 14071 to 1407n. 
On receipt of the grants from the scheduler 1405, the input buffers 14021 to 1402n transfer the packets stored therein to the switch 1406. The switch 1406 switches the thus received packets, and transmits the packets to the output ports 14071 to 1407n. Thus, there is accomplished a function of switching a packet.
In the input buffer type switch, the scheduler 1405 schedules the output ports 14071 to 1407n in accordance with a predetermined algorithm, based on the requests 14041 to 1404n transmitted from the input buffers 14021 to 1402n. Accordingly, if the requests 14041 to 1404n transmitted from the input buffers 14021 to 1402n have the same order of precedence, a frequency of operating the switch 1406 becomes non-uniform among the input ports 14011 to 1401n. 
Japanese Unexamined Patent Publication No. 5-292116 has suggested a control circuit for controlling an input buffer type ATM switch. The control circuit is comprised of means for reading addresses of a plurality of cells out of a header of FIFO memory, a table which manages transmission of cells from FIFO memory by every cell period, and means for transmitting a signal to request transmission of cells which signal includes addresses of cells, receiving response signals including a time at which a cell is to be output, reserving transmission of a cell from FIFO memory at a designated time at which a cell is to be output, with reference to the table, and outputting a cell from FIFO memory at the time. After a signal to request transmission of a cell has been transmitted, but before a cell is transmitted, a signal to request transmission of a next cell is transmitted. The suggested control circuit can receive packets from a high-rate input port, and absorb variance in both a process time in circuits and a delay time in signal transmission in circuits.
Japanese Unexamined Patent Publication No. 9-168016 has suggested a packet switch including an input buffer and an output buffer. The output buffer is designed to include a plurality of buffer areas shared by a plurality of output ports, and the input buffer is designed to include a logic queue associated with a combination of the buffer areas. An input controller inputs a multi-cast packet into a logic queue associated with a combination including a buffer area associated with an output port to which the multi-cast packet is addressed, and then, a scheduler and a switch transfer the multi-cast packet to a buffer area connected to the output port to which the multi-cast packet is addressed. Then, the multi-cast packet is transferred to the output port from the buffer area. Thus, it is possible to transfer multi-cast packets without an increase in packets to be transferred to the output buffer from the input buffer, and further without a problem of HOL blocking.
Japanese Patent No. 2967767 (Japanese Unexamined Patent Publication No. 11-68770) has suggested a scheduler used in ATM switch. The scheduler includes a cell selector which selects a cell to be output, based on a weight in each of classes and the number of accumulate queues. Specifically, the cell selector selects a class having a higher priority than others, with reference to predetermined priority of each of classes. That is, a higher priority is assigned to a traffic class required to have delay characteristic, and a class having a higher priority than others is selected in preference when an output queue is selected in rotational preference control. Thus, it would be possible to output a cell without waiting other cells having a lower priority being output. As a result, even if traffic classes to be accumulated were increased in number, it would be possible to reduce degradation in delay characteristic of a traffic class which is required to have real time characteristic, ensuring that CDV characteristic is avoided from being harmfully influenced.